TNotes.leetcode

Appearance

0257. 二叉树的所有路径【简单】

0257. 二叉树的所有路径【简单】 ​

1. 📝 题目描述 ​

给你一个二叉树的根节点 root，按 任意顺序，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

img

txt
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

txt
输入：root = [1]
输出：["1"]

提示：

  • 树中节点的数目在范围 [1, 100] 内
  • -100 <= Node.val <= 100

2. 🎯 s.1 - 递归 + 回溯 ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
  const result = []

  if (!root) return result

  dfs(root, [], result)

  return result
}

function dfs(node, path, result) {
  if (!node) return

  // 将当前节点加入路径
  path.push(node.val)

  // 如果是叶子节点，将路径加入结果集
  if (!node.left && !node.right) {
    result.push(path.join('->'))
  } else {
    // 递归遍历左右子树
    dfs(node.left, path, result)
    dfs(node.right, path, result)
  }

  // 回溯，移除当前节点
  path.pop()
}
  • 时间复杂度：O(n2)，其中 n 是节点数，最坏情况下每条路径有 n 个节点，共有 n 条路径
  • 空间复杂度：O(n)，递归调用栈和路径数组的空间
  • 算法思路：
    • 这道题要求返回从根节点到所有叶子节点的路径。我们需要遍历二叉树，记录从根节点到每个叶子节点的路径。
    • 可以使用深度优先搜索（DFS）配合回溯的方法来解决：
      1. 从根节点开始遍历
      2. 记录当前路径
      3. 当到达叶子节点时，将当前路径加入结果集
      4. 回溯时需要移除当前节点，保证路径的正确性

3. 🎯 s.2 - 递归（传递路径字符串） ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
  const result = []

  if (!root) return result

  dfs(root, '', result)

  return result
}

function dfs(node, path, result) {
  if (!node) return

  // 构建当前路径字符串
  const currentPath = path ? path + '->' + node.val : String(node.val)

  // 如果是叶子节点，将路径加入结果集
  if (!node.left && !node.right) {
    result.push(currentPath)
  } else {
    // 递归遍历左右子树
    dfs(node.left, currentPath, result)
    dfs(node.right, currentPath, result)
  }
}
  • 时间复杂度：O(n2)，字符串拼接操作
  • 空间复杂度：O(n2)，每次递归都创建新的字符串
  • 算法思路：类似解法 1

4. 🎯 s.3 - 迭代（使用栈） ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
  const result = []

  if (!root) return result

  // 栈中存储 [节点, 路径] 对
  const stack = [[root, String(root.val)]]

  while (stack.length > 0) {
    const [node, path] = stack.pop()

    // 如果是叶子节点，将路径加入结果集
    if (!node.left && !node.right) {
      result.push(path)
    }

    // 将子节点和对应路径加入栈中
    if (node.right) {
      stack.push([node.right, path + '->' + node.right.val])
    }

    if (node.left) {
      stack.push([node.left, path + '->' + node.left.val])
    }
  }

  return result
}
  • 时间复杂度：O(n2)
  • 空间复杂度：O(n2)，栈中存储路径字符串
  • 算法思路：和上述解法类似，但没有用到递归，而是使用循环来模拟递归流程

Discussions